package features.advance.leetcode.array.easy;

/**
 *  剑指 Offer 53 - II. 0～n-1中缺失的数字
 *
 *  难度：简单
 *
 * 一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
 *
 *
 *
 * 示例 1:
 *
 * 输入: [0,1,3]
 * 输出: 2
 * 示例 2:
 *
 * 输入: [0,1,2,3,4,5,6,7,9]
 * 输出: 8
 *
 *
 * 限制：
 *
 * 1 <= 数组长度 <= 10000
 *
 * @author LIN
 * @date 2021-05-27
 */
public class Offer53_2 {

    public static void main(String[] args) {
        Solution solution = new Solution() {
        };
        int[] nums = {0,1,2,3,5,6,7,8,10};
        int res = solution.missingNumber(nums);
        System.out.println(res);
    }

    static class Solution {
        /**
         * 思路：
         * @param nums
         * @return
         */
        public int missingNumber(int[] nums) {
            int i = 0, j = nums.length - 1;
            while (i <= j) {
                int m = (i + j) / 2;
                if (nums[m] == m){
                    i = m + 1;
                } else {
                    j = m - 1;
                }
            }
            return i;
        }
    }
}
